
// 1. dfs解法，会超时
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1005;

int triangles[N][N];
int r;

int DFS(int x, int y)
{
    if (x > r || y > r)
        return 0;
    else
        return triangles[x][y] + max(DFS(x + 1, y), DFS(x + 1, y + 1));
}

int main()
{
    scanf("%d", &r);
    for (int i = 1; i <= r; ++i)
    {
        for (int j = 1; j <= i; ++j)
        {
            scanf("%d", &triangles[i][j]);
        }
    }

    int res = DFS(1, 1);

    printf("%d\n", res);

    return 0;
}

// 2.记忆化搜索解法，也会超时
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1005;

int triangles[N][N];
int r;
int mem[N][N];

int DFS(int x, int y)
{
    if (mem[x][y])
        return mem[x][y];
    int sum;
    if (x > r || y > r)
        sum = 0;
    else
        sum = triangles[x][y] + max(DFS(x + 1, y), DFS(x + 1, y + 1));

    mem[x][y] = sum;

    return sum;
}

int main()
{
    scanf("%d", &r);
    for (int i = 1; i <= r; ++i)
    {
        for (int j = 1; j <= i; ++j)
        {
            scanf("%d", &triangles[i][j]);
        }
    }

    int res = DFS(1, 1);

    printf("%d\n", res);

    return 0;
}

// 3.动态规划解法，ac
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1005;

int triangles[N][N];
int r;
int f[N][N];

int main()
{
    scanf("%d", &r);
    for (int i = 1; i <= r; ++i)
    {
        for (int j = 1; j <= i; ++j)
        {
            scanf("%d", &triangles[i][j]);
        }
    }

    for (int i = r; i > 0; --i)
    {
        for (int j = i; j > 0; --j)
        {
            f[i][j] = triangles[i][j] + max(f[i + 1][j], f[i + 1][j + 1]);
        }
    }

    printf("%d\n", f[1][1]);

    return 0;
}

// 3.动态规划解法 + 优化为一维数组
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1005;

int triangles[N][N];
int r;
int f[N];

int main()
{
    scanf("%d", &r);
    for (int i = 1; i <= r; ++i)
    {
        for (int j = 1; j <= i; ++j)
        {
            scanf("%d", &triangles[i][j]);
        }
    }

    for (int i = r; i > 0; --i)
    {
        for (int j = 1; j <= i; ++j)
        {
            f[j] = triangles[i][j] + max(f[j], f[j + 1]);
        }
    }

    printf("%d\n", f[1]);

    return 0;
}